package cn.suchan.jianzhi.q38_tree;

import java.util.ArrayList;

/**
 * 知识点：二叉树的深度
 * 题目描述
 * 输入一棵二叉树，求该树的深度。
 * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
 *
 * @author suchan
 * @date 2019/06/03
 */
public class Solution {

    private int depth = 0;
    private int max = 0;

    /**
     * 这个方法比较麻烦
     *
     * @param root
     * @return
     */
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 存储所有节点路径（从根节点到任意叶子节点）
        ArrayList<ArrayList<TreeNode>> pathList = new ArrayList<>();
        // 把根节点存进去，作为第一个路径
        ArrayList<TreeNode> nodeList = new ArrayList<>();
        nodeList.add(root);
        pathList.add(nodeList);

        for (int i = 0; i < pathList.size(); i++) {
            ArrayList<TreeNode> treeNodes = pathList.get(i);
            // 获取路径中最后一个节点
            TreeNode node = treeNodes.get(treeNodes.size() - 1);
            // 如果该节点是叶子结点，说明是该路径最后一个节点了，就不用进行操作了
            if (node.left != null || node.right != null) {
                // 如果左节点不为空，则把原来节点复制出来，并把左节点加进入
                if (node.left != null) {
                    ArrayList<TreeNode> treeNodes1 = new ArrayList<>();
                    treeNodes1.addAll(treeNodes);
                    treeNodes1.add(node.left);
                    pathList.add(treeNodes1);
                }
                // 如果右节点不为空，则把原来节点复制出来，并把右节点加进入
                if (node.right != null) {
                    ArrayList<TreeNode> treeNodes2 = new ArrayList<>();
                    treeNodes2.addAll(treeNodes);
                    treeNodes2.add(node.right);
                    pathList.add(treeNodes2);
                }

                // 由于当前节点不是叶子结点，且其左右节点已经复制原来的路径并加进入pathList了，所以需要把原来的路径去掉
                pathList.remove(treeNodes);
                // 去掉之后它原本的位置就是新的路径了，所以要在i变成i++之前进行i--，保持i的位置不变
                i--;
            }
        }

        // 获取所有路径中最长的路径长度就是该树的深度
        int maxPath = 0;
        for (ArrayList<TreeNode> paths : pathList) {
            if (paths.size() > maxPath) {
                maxPath = paths.size();
            }
        }

        return maxPath;
    }

    /**
     * 递归方式
     *
     * @param root
     * @return
     */
    public int TreeDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 该节点不为空，则节点深度++
        depth++;
        TreeDepth1(root.left);
        if (depth > max) {
            max = depth;
        }
        TreeDepth1(root.right);
        if (depth > max) {
            max = depth;
        }
        // 到此，左右节点已遍历完毕，回到上一个节点
        depth--;
        return max;
    }

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.left = node8;
        node5.right = node9;
        node9.right = node10;

        Solution solution = new Solution();
        System.out.println(solution.TreeDepth1(node1));
    }
}
